The present invention relates to optical computing and image and pattern recognition systems and techniques in general and, more particularly, to an optical architecture for accomplishing real-time two-dimensional pattern recognition by implementing the so-called "Mean-Square-Error" correlation algorithm (also referred to as the "Difference-Squared Error" algorithm) for discriminating, i.e., recognizing two-dimensional patterns in gray-scale images.
Previously, real-time electronic and optical architectures for pattern recognition have utilized basic correlation (and convolution) operations for discriminating desired objects (targets and image patterns of interest) from unwanted objects and residual background "clutter" in an input scene being imaged.
However, basic correlation methods do not perform particularly well in processing certain gray-level input scenes and input scenes with high average value background levels such as encountered in automatic target recognition environments, making correlators unsuitable for solving certain image recognition problems. For example, a bright spot in the input scene, such as might be caused by a flare or a bright background feature, can produce a large correlation peak thereby causing the recognition system to incorrectly indicate the presence of an object or target in the input scene. Edge-enhancement processing may in some cases be beneficial for avoiding such false indications, however, then the gray level characteristics of the signals are lost while the background noise tends to be emphasized. Thus, the target recognition environment has proven to be a particularly difficult area for correlation-based pattern recognition systems.
Another technique for performing two-dimensional pattern recognition known as the "difference-squared error" (DSE) algorithm method involves computing the squared difference of a reference template, R(x,y), over the entire region of a larger input image, I(x,y). If it is assumed that the input image is N.times.N pixels in dimension and that the reference template is M.times.M pixels in size, the difference-squared error can be expressed as: EQU DSE(n.sub.x,n.sub.y)=.intg.M.sub.y .intg.M.sub.x [I(m.sub.x +n.sub.x,m.sub.y +n.sub.y)-R(m.sub.x,m.sub.y)].sup.2 dm.sub.x dm.sub.y( 1)
Equation (1) can be used to find the difference-squared error between the reference template and the input image at every location in the input image. When a segment in the input image exactly matches the reference template, the difference will be zero (0) and the resulting value in the difference-squared error matrix, DSE (n.sub.x, n.sub.y), will also be zero. When the input image segment differs from the template by some amount, the magnitude of the result indicates the degree of this mismatch.
The difference-squared error algorithm can provide much better discrimination of gray-level objects than correlation. For example, when a triangle-shaped signal as shown in FIG. 1(a) is correlated with itself and with the square-shaped signal in FIG. 1(b), the results are as shown in FIGS. 1(c) and 1(d), respectively. As may be seen from these figures, the correlation operation between the triangular signal and the square signal produces a higher correlation peak than does the auto-correlation of the triangular signal with itself. And therefore the triangle-shaped signal can not be discriminated from the square-shaped signal by thresholding the output of the correlation even when, as shown by the dashed line in FIGS. 1(c) and 1(d), the match-mismatch correlation threshold is set proximate the apex of the auto-correlation peak.
However, if the DSE algorithm is applied to the same signals, the results are quite different. As shown in FIG. 1(e), the result of the DSE correlation performed between the two triangle-shaped signals produces an output of zero indicating a no-error or match condition between these two signals. But when the DSE correlation operation is performed between the square and triangle signals, a large mismatch is present producing a large error result. This causes the resultant output level as shown in FIG. 1(f) to be well above the dashed line threshold level. A simple thresholding operation can then be used to discriminate between the DSE outputs of FIGS. 1(e) and 1(f). Thus, the DSE algorithm can provide much better discrimination of gray-scale inputs than can the basic correlation technique.
For implementing the DSE algorithm, it is convenient to rewrite equation (1) by expanding the terms therein as follows: EQU DSE(n.sub.x,n.sub.y)=.intg.M.sub.y .intg.M.sub.x [I.sup.2 (m.sub.x +n.sub.x, m.sub.y +n.sub.y)+R.sup.2 (m.sub.x, m.sub.y)-2I(m.sub.x +n.sub.x, m.sub.y +n.sub.y) R(m.sub.x, m.sub.y ]dm.sub.x dm.sub.y( 2)
The three terms in equation (2) can be generated using correlation. The first term represents the auto-correlation of the input image. The second term is the auto-correlation of the reference template. The third term is proportional to the cross-correlation of the input image with the reference template. It has been suggested that this difference squared operation can be performed in real-time using a fast electronic or optical correlator to compute the input-dependent terms, I.sup.2 ( ) and 2I( )R( ). Since the second term, R.sup.2 ( ), is only a function of the reference template, it can be generated a priori. The results of these three correlations can then be added or subtracted electronically to produce the desired difference-squared result in real time. However, such an implementation poses formidable computational problems.
In order to compute DSE algorithm equation (2) in real-time, the processor must be capable of maintaining an extremely high throughput rate yet must also maintain a large number of bits of precision. For every new input image or reference template to be processed, a new correlation must be performed. For large input images, this computation involves processing enormous amounts of data.
For example, a common target recognition scenario involves images that are 512.times.512 pixels in size, and reference templates that are 64.times.64 pixels in size. Computational problems of this magnitude require more than one billion operations (i.e. multiply/adds) to be performed for obtaining a single difference-squared result. At an image frame input rate of 30 frames per second, this requires more than 6.times.10.sup.10 operations to be performed per second for real-time processing. This throughput rate is required for comparing only one reference template against an input image. In typical situations, the object of interest may have an arbitrary orientation (and size) in the input scene, so that many different rotated (and possibly also scaled) versions of the reference template must be tried against the same input image. If only as few as forty (40) different templates are required to take into account these variances, the throughput rate requirement will then exceed 10.sup.12 operations per second. Furthermore, since each pixel in the input image and the reference templates represents gray-level values, typically 8-bit data quantities, each term in equation (2) must accommodate up to 28 bits of precision for a template that is 64.times.64 pixels in size. These processing requirements are formidable for any system to meet; however, for automatic target recognition applications the high throughput processor must also satisfy stringent size, weight and power consumption restrictions. Electronic processing architectures have great difficulty in simultaneously meeting all of the requirements for high speed, high degree of computational precision and a restricted operating environment. Thus, problems have remained in implementing this technique with electronic architectures.
Optical processing architectures are particularly well-suited to problems involving large two-dimensional arrays of data, especially for correlation-based pattern recognition, see for example: Rhodes, W. T., "Acousto-optic signal processing: convolution and correlation", Proc. IEEE, Vol. 69, No. 1, pp. 65-78 (January 1981) and Vander Lugt, A., "Signal detection by complex spatial filtering", IEEE Trans. Inf. Theory IT-10, (2), pp. 139-145 (1964). In addition, the latest generation of optical devices provides the opportunity to construct processors ideally suited for the embedded computer environment because of their potential size, weight and power consumption advantages. See, for example: Stalker, K. T. et al., "A compact, real-time acousto-optic synthetic aperture radar image processor", Proc. SPIE (1989) (SPIE 1989 Technical Symposium, Orlando, Fla., March 1989).
However, optical correlator architectures are not able to achieve the required precision because of the inherent limitations in the dynamic range of available photodetecting devices. If an optical correlator were used for computing each of the signal-dependent terms in equation (2) above, the Lo-bits of dynamic range, which is typical for many CCD (charge-coupled device) photodetectors, would not be sufficient to obtain an accurate result. For example, when an exact template match is found in the input image, the result of the three correlation operations in equation (2) produces three relatively large numbers that, when subtracted, give a zero result. Since after this subtraction the concern will be with relatively small numbers, the correlation terms must keep a high degree of precision in order to preserve the integrity of the lower-order bits. Present detectors fall far short of the 28-bits of needed dynamic range. Thus, optical processing architectures have not proven satisfactory for this task, and the need has remained for a more suitable means for discriminating patterns from gray-level input images.
The mean-square-error (MSE) correlation algorithm has been implemented for many years on large electronic computers to recognize objects of interest in gray-level input scenes and can also provide enhanced performance over correlators for discriminating object image features in gray-level input scenes and in input images having high average background values.
The two-dimensional MSE pattern recognition algorithm for an input image I(x,y) having a size of N.times.N, and a reference template R(x,y) having a size of M.times.M is given as follows: EQU MSE=.SIGMA.[I-R].sup.2 ( 3)
and can be evaluated for MSE(n.sub.x, n.sub.y) which is given by: ##EQU1## so that MSE(n.sub.x, n.sub.y) can be further expressed as: ##EQU2## where the third term (.SIGMA..SIGMA.2 I R) in equation (5) is the correlation of the input image I(x,y) with the reference template R(x,y) times a constant, the second term (R.sup.2) is a constant term for each template, and the first term (I.sup.2) is the correlation of the input image squared with a constant unity template.
Because of the large amount of image data which must necessarily be processed in performing the computations involved in implementing the MSE algorithm on even the smallest input reference image templates, such previous implementations must use floating point arithmetic in order to keep track of the result with the necessary precision required. However, presently available electronic processors using floating point arithmetic are not able to attain the high throughput rates necessary for processing input image data in "virtual" real-time mode.
In accordance with the present invention, it is now made possible to perform the MSE operation in one step using a modified optical correlator implementation. This implementation overcomes the serious dynamic range problems encountered by forming the result as the difference of correlation products.
By way of introduction, it is helpful to first briefly describe an implementation of the DSE algorithm on an optical architecture. The basic element needed for computing the difference-squared error is the time-integrating optical correlator. A one-dimensional (1-D) correlation between a reference template, R(t), and an input signal, I(t), is defined by: EQU C(.tau.)=.intg..sub.T R(t) I(t+.tau.)dt (6)
where T is the duration of the reference signal. This can be implemented in an acousto-optic architecture as shown in FIG. 2 [see also: Psaltis, D., "Two-dimensional optical processing using one-dimensional input devices," Proc. IEEE 72(7), pp. 962-974, (1984), and Kellman, "Time Integrating Optical Signal Processing", pp. 51-55, (Ph. D. Thesis), Stanford University (1979).
In the architecture of FIG. 2, the intensity of the diode light source D is temporally modulated. The light from the diode D is collimated by the first lens L1 and illuminates the aperture of the acousto-optic device AOD. The electrical signal I(t) is mixed to the center frequency of the cell and applied to the input transducer of the AOD where it is converted into a time-delayed spatial modulation. The carrier offset causes the diffracted order to contain the desired signal, I(t+.tau.). In this form, .tau.=x/v where v is the speed of sound in the cell and x is the dimension in the direction of acoustic propagation. The undiffracted light is blocked by a D. C. stop S. The spatial distribution is then imaged onto a detector plane of a detector array A (e.g., a CCD). If the diode D is driven by a time-varying signal R(t) as the information I(t) propagates down the length of the AOD, then the charge accumulated on the detector array A will be proportional to the correlation of the two signals R(t) and I(t). This one-dimensional time integrating optical correlator uses incoherent light, and therefore only positive real values can be represented. To overcome this limitation, signals are placed on a bias. This bias causes cross-correlation products to appear in the correlation result thereby degrading the peak-to-sidelobe ratio of the correlation peak as has been shown from Molley, P. A., et al., "A high dynamic range acousto-optic image correlator for real time pattern recognition," Proc. SPIE, Vol. 938, pp. 55-65 (1988).
However, it has been found that these same bias terms can be beneficial for forming the difference-squared error result, if the form of the input signals is modified. An implementation of the DSE algorithm on an optical architecture is described in Molley, P. A., "Implementing the difference-square error algorithm using an acousto-optic processor," SPIE Vol. 1098, pp. 232-239, (1989) (SPIE 1989 Technical Symposium, Orlando, Fla., March 1989), the substance of which is hereby incorporated herein by reference thereto.
A real-time incoherent light optical image correlator also has been described using an acousto-optic device and an array of light-emitting diodes as electronic-to-optical transducers for the input and reference images, respectively, in an optical correlator architecture, with a two-dimensional correlation being formed by temporal integration on a two-dimensional CCD detector array. See, Psaltis, "Incoherent electro-optic image correlator," Optical Engineering, Vol. 23, No. 1, pp. 12-15, (1984), the disclosure of which is hereby incorporated by reference thereto.
In accordance with the present invention, it has now been made possible to implement the MSE algorithm on an optical architecture in order to obtain real-time MSE processing for pattern recognition. This is most desirable from a performance standpoint, in that the MSE algorithm is a very powerful and accurate means of discriminating patterns for locating objects in gray-level input images, providing results which are at least equivalent to those obtained with the DSE algorithm.
In order to demonstrate the feasibility of such an optical architecture for implementing the MSE algorithm, a one-dimensional timeintegrating optical correlator was constructed for implementing the MSE algorithm in an optical correlator architecture. By selectively and specifically modifying the signals applied to the diode light source and the acousto-optic deflector as will be more fully described in detail below, it is made possible to implement the MSE algorithm in real-time using an acoustooptic processor. The implementation makes maximum use of the available dynamic range of the CCD because the contribution of bias terms resulting during the processing operation is utilized as desirable terms for implementing the MSE algorithm. These bias terms produce a charge on the CCD from which the correlation term is subtracted.
Furthermore, by employing "anti-blooming" gates on the CCD detector, the dynamic range of the CCD can be utilized in the range of the expected result, and since the desired result occurs as the lowest (i.e., least charge) value, the dynamic range of the CCD detector may conveniently be fixed to this value. The various system parameters, such as the relative diode intensity, can be set to allow the expected result to fall within the dynamic range of the CCD detector. And by setting the desired result to be a low value, it is possible to ignore any large cross-correlation products which may saturate individual pixel elements of the CCD detector. Computer simulations of pattern recognition processes have indicated that the MSE algorithm correlation technique results exactly match those obtained with the DSE algorithm, with the results obtained by both the DSE algorithm and the MSE algorithm techniques being far superior to the correlation method when certain types of noise and background clutter are present in the input image. The results of these simulations are more fully described below.
Electro-optical devices of the "matched filtering" type are known which make use of optical filters having mean-square error characteristics for providing a desired optical transfer function, for example from U.S. Pat. No. 3,947,123 which discloses the provision and use of an optical filter having minimum mean-square error linear characteristics in a coherent optical analyzer for identifying biological cells, and from U.S. Pat. No. 4,067,645 which discloses forming a minimum mean-square error linear filter photographically. Also known is U.S. Pat. No. 4,082,431 which discloses an image processing system using incoherent radiation and a spatial hologram filter having a linear minimum mean-square error response and the use of such a system for pattern recognition by matched filtering of input images.
However, there have been no previous proposals for implementing the mean square-error (MSE) correlation algorithm in real-time using an optical architecture or an acousto-optical architecture as in the present invention.
It is therefore an object of the present invention to provide an optical correlator architecture implementing the MSE algorithm for pattern recognition which is amenable to construction in a compact, light-weight, low power configuration and which lends itself to the embedded computer environment.
It is further an object of the present invention to provide an implementation of the MSE algorithm using an optical time-integrating correlator for pattern recognition in gray-level input images.
It is still further an object of the present invention to provide an implementation of the MSE algorithm on an optical architecture for processing an input image in one pass in real time.
It is still another object of the present invention to provide an implementation of the MSE algorithm on an optical architecture which can be used for two-dimensional pattern recognition.
It is yet further an object of the present invention to implement the MSE algorithm on an optical architecture making maximum use of the available dynamic range of a CCD photodetector.
The features, objects and advantages of the present invention will be made more apparent from the following detailed description taken together with the accompanying drawings.